class Solution(object):
    def findBestValue(self, arr, target):
        t = sum(arr)
        if t <= target:
            return max(arr)
        left = 0
        right = max(arr)
        min_diff = abs(t - target)
        min_val = right

        def cal(val):
            return sum([val if num >= val else num for num in arr])

        while left <= right:
            mid = (left + right) // 2
            total = cal(mid)
            if abs(target - total) < min_diff:
                min_diff = abs(target - total)
                min_val = mid
            else:
                if abs(target - total) == min_diff:
                    min_val = min(min_val, mid)
            if total == target:
                break
            if total < target:
                left = mid + 1
            else:
                right = mid - 1
        return min_val

